package com.dmall.graph.bfs.app;

import java.util.*;

public class Leetcode752 {

    private static final String source = "0000";

    public int openLock(String[] deadends, String target) {
        Set<String> deadendSet = new HashSet<>();
        for (String deadend : deadends) {
            deadendSet.add(deadend);
        }

        if (deadendSet.contains(target) || deadendSet.contains(source)) {
            return -1;
        }
        if (source.equals(target)) {
            return 0;
        }
        Map<String, Integer> map = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(source);
        map.put(source, 0);
        while (!queue.isEmpty()) {
            String cur = queue.remove();
            List<String> nexts = getNexts(cur);
            for (String next : nexts) {
                if (!deadendSet.contains(next) && !map.containsKey(next)) {
                    queue.add(next);
                    map.put(next, map.get(cur) + 1);

                    if (next.equals(target)) {
                        return map.get(next);
                    }
                }
            }
        }
        return -1;
    }

    private List<String> getNexts(String lock) {
        List<String> res = new ArrayList<>(4);
        char[] chars = lock.toCharArray();
        for (int i = 0; i < 4; i++) {
            char c = chars[i];
            chars[i] = Character.forDigit((chars[i] - '0' + 1) % 10, 10);
            res.add(new String(chars));
            chars[i] = c;

            chars[i] = Character.forDigit((chars[i] - '0' + 9) % 10, 10);
            res.add(new String(chars));
            chars[i] = c;
        }
        return res;
    }

    public static void main(String[] args) {
        String[] deadends = {"0201","0101","0102","1212","2002"};
        String target = "0202";
        // String[] deadends = {"8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"};
        // String target = "8888";
        Leetcode752 leetcode752 = new Leetcode752();
        System.out.println(leetcode752.openLock(deadends, target));
    }
}
